/* vim: set sw=8 ts=8 sts=8 expandtab: */
/* the original implementation is take from OpenBSD and was adjust to be
 * used in side of cmaid, this file is not covered by the project licence of
 * cmaid, but under the conditions of the licence used by the original
 * implementation */
/*-
 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
 *           2008 Peter Wehrfritz <peter.wehrfritz@web.de>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
#include "Cmaid.h"
#include "cmaid_private.h"

/**
 * @defgroup Cmaid_Tree The Tree Implementation
 * @ingroup Implementations
 * @brief The tree implemenation
 *
 * The tree implementation is a red-black tree. It is lexically ordered. The
 * operations for insertion, removes and look-ups, is guaranteed to be
 * @em O(log N). The average memory usage is higher then for hash table. Hence
 * it is preferable in most cases to use a hash table, as long as you don't
 * need the lexically order or a good hash function is hard to figure out.
 */

#define RB_BLACK        0
#define RB_RED          1

typedef struct Cmaid_Tree Cmaid_Tree;
typedef struct Cmaid_Tree_Node Cmaid_Tree_Node;
typedef struct Cmaid_Tree_Cache_Node Cmaid_Tree_Cache_Node;
typedef struct Cmaid_Tree_Map Cmaid_Tree_Map;
typedef struct Cmaid_Tree_Node_Pair Cmaid_Tree_Node_Pair;

#define CMAID_TREE(h) ((Cmaid_Tree *)(h))
#define CMAID_TREE_NODE(n) ((Cmaid_Tree_Node *)(n))
#define CMAID_TREE_CACHE_NODE(n) ((Cmaid_Tree_Cache_Node *)(n))
#define CMAID_TREE_CACHE_NODE_COUNT(n) CMAID_TREE_CACHE_NODE(n)->count
#define CMAID_TREE_MAP_VALUE_INFO(h) ((Cmaid_Tree_Map *)(h))->value_info
#define CMAID_TREE_MAP_NODE_VALUE(n) ((Cmaid_Tree_Node_Pair *)(n))->value

/**
 * @internal
 * Node for the tree
 */
struct Cmaid_Tree_Node
{
        Cmaid_Tree_Node *left;   /* left element */
        Cmaid_Tree_Node *right;  /* right element */
        Cmaid_Tree_Node *parent; /* parent element */
        void *key;               /* The key for the data node */
        int color;               /* node color */
};

#define RB_LEFT(elm)            (elm)->left
#define RB_RIGHT(elm)           (elm)->right
#define RB_PARENT(elm)          (elm)->parent
#define RB_COLOR(elm)           (elm)->color
#define RB_IS_BLACK(elm)        (!elm || (elm)->color == RB_BLACK)
#define RB_IS_RED(elm)          (elm && (elm)->color == RB_RED)

struct Cmaid_Tree_Cache_Node
{
        Cmaid_Tree_Node node;
        unsigned int count;
};

struct Cmaid_Tree_Node_Pair
{
        Cmaid_Tree_Node node;
        void *value;
};

struct Cmaid_Tree
{
        Cmaid_Container container;
        Cmaid_Tree_Node *root;  /* the root of the tree */
        Cmaid_Iter *iter_list;
        const Cmaid_Value *key_info;
};

struct Cmaid_Tree_Map
{
        Cmaid_Tree tree;
        const Cmaid_Value *value_info;
};

/* Private tree manipulation functions */
static unsigned int cmaid_tree_node_get(Cmaid_Tree *tree, const void *key,
                                        Cmaid_Tree_Node **find);
static void cmaid_tree_node_insert(Cmaid_Tree *tree, Cmaid_Tree_Node *node,
                                        Cmaid_Tree_Node *parent);
static Cmaid_Tree_Node *cmaid_tree_node_remove(Cmaid_Tree *tree,
                                        Cmaid_Tree_Node *node);
CMAID_INLINE void cmaid_tree_node_repair(Cmaid_Tree *tree,
                                        Cmaid_Tree_Node *node,
                                        Cmaid_Tree_Node *new_node);
static void cmaid_tree_iter_update_remove_index(Cmaid_Tree *tree,
                                        Cmaid_Tree_Node *node, int index);
static void cmaid_tree_iter_update_remove_data(Cmaid_Tree *tree,
                                        Cmaid_Tree_Node *node);
static void cmaid_tree_iter_update_insert(Cmaid_Tree *tree,
                                        Cmaid_Tree_Node *node);
static Cmaid_Tree_Node *cmaid_tree_node_next(Cmaid_Tree_Node *node);
static Cmaid_Tree_Node *cmaid_tree_node_previous(Cmaid_Tree_Node *node);
/* The common interface functions */
static void  cmaid_tree_iter_attach(Cmaid_Container *c, Cmaid_Iter *it);
static void  cmaid_tree_iter_detach(Cmaid_Container *c, Cmaid_Iter *it);
static void  cmaid_tree_destroy(Cmaid_Container *c);
static int   cmaid_tree_dump(Cmaid_Container *c, FILE *file);
static void  cmaid_tree_clear(Cmaid_Container *c);
/* The set interface functions */
static void *cmaid_tree_set_add(Cmaid_Set *s, const void *data);
static void  cmaid_tree_set_remove(Cmaid_Set *s, const void *data);
static void *cmaid_tree_set_get(Cmaid_Set *s, const void *data);
CMAID_INLINE void cmaid_tree_single_node_free(Cmaid_Container *c, void *node);
/* The map interface functions */
static void *cmaid_tree_map_set(Cmaid_Map *m, const void *key,
                                const void *data);
static void  cmaid_tree_map_remove(Cmaid_Map *m, const void *key);
static void *cmaid_tree_map_get(Cmaid_Map *m, const void *key);
static void  cmaid_tree_map_value_iter_attach(Cmaid_Map *m, Cmaid_Iter *it);
CMAID_INLINE void cmaid_tree_map_node_free(Cmaid_Container *c, void *n);

/* The common iterator interface functions */
static void  cmaid_tree_iter_start(Cmaid_Iter *it);
static void  cmaid_tree_iter_remove(Cmaid_Iter *it);
/* The key iter functions */
static void *cmaid_tree_key_iter_iter_goto(Cmaid_Iter *it, const Cmaid_Iter *to_it);
static void *cmaid_tree_key_iter_index_goto(Cmaid_Iter *it, int index);
static void *cmaid_tree_key_iter_goto(Cmaid_Iter *it, const void *data);
static void *cmaid_tree_key_iter_current(Cmaid_Iter *it);
static void *cmaid_tree_key_iter_next(Cmaid_Iter *it);
static void *cmaid_tree_key_iter_previous(Cmaid_Iter *it);
/* The value iter functions */
static void *cmaid_tree_value_iter_iter_goto(Cmaid_Iter *it, const Cmaid_Iter *to_it);
static void *cmaid_tree_value_iter_index_goto(Cmaid_Iter *it, int index);
static void *cmaid_tree_value_iter_goto(Cmaid_Iter *it, const void *data);
static void *cmaid_tree_value_iter_current(Cmaid_Iter *it);
static void *cmaid_tree_value_iter_next(Cmaid_Iter *it);
static void *cmaid_tree_value_iter_previous(Cmaid_Iter *it);
/* Iter helper */
static Cmaid_Tree_Node *cmaid_tree_iter_next(Cmaid_Iter *it);
static Cmaid_Tree_Node *cmaid_tree_iter_previous(Cmaid_Iter *it);

/*
 * The Interfaces
 */
const Cmaid_Set_Interface cmaid_tree_set_if =
{
        {
                CMAID_MAGIC_SET,
                cmaid_tree_clear,
                cmaid_tree_iter_attach,
                cmaid_tree_iter_detach,
                cmaid_tree_destroy,
                cmaid_tree_dump,
                cmaid_tree_single_node_free
        },
        cmaid_tree_set_add,
        cmaid_tree_set_remove,
        cmaid_tree_set_get
};

const Cmaid_Map_Interface cmaid_tree_map_if =
{
        {
                CMAID_MAGIC_MAP,
                cmaid_tree_clear,
                cmaid_tree_iter_attach,
                cmaid_tree_iter_detach,
                cmaid_tree_destroy,
                cmaid_tree_dump,
                cmaid_tree_map_node_free
        },
        cmaid_tree_map_set,
        cmaid_tree_map_remove,
        cmaid_tree_map_get,
        cmaid_tree_map_value_iter_attach
};

const Cmaid_Iter_Interface cmaid_tree_key_iter_if =
{
        cmaid_tree_iter_start,
        cmaid_tree_key_iter_iter_goto,
        cmaid_tree_key_iter_index_goto,
        cmaid_tree_key_iter_goto,
        cmaid_tree_key_iter_current,
        cmaid_tree_key_iter_next,
        cmaid_tree_key_iter_previous,
        cmaid_tree_iter_remove
};

const Cmaid_Iter_Interface cmaid_tree_value_iter_if =
{
        cmaid_tree_iter_start,
        cmaid_tree_value_iter_iter_goto,
        cmaid_tree_value_iter_index_goto,
        cmaid_tree_value_iter_goto,
        cmaid_tree_value_iter_current,
        cmaid_tree_value_iter_next,
        cmaid_tree_value_iter_previous,
        cmaid_tree_iter_remove 
};

/*
 * Node Functions
 */
CMAID_INLINE void
cmaid_tree_single_node_free(Cmaid_Container *c, void *n)
{
        Cmaid_Tree *tree = CMAID_TREE(c);
        Cmaid_Tree_Node *node = n;
        cmaid_single_node_free(node, tree->key_info, node->key);
}

CMAID_INLINE void
cmaid_tree_map_node_free(Cmaid_Container *c, void *n)
{
        Cmaid_Tree *tree = CMAID_TREE(c);
        Cmaid_Tree_Node *node = n;
        cmaid_pair_node_free(node, tree->key_info, node->key,
                                CMAID_TREE_MAP_VALUE_INFO(tree),
                                CMAID_TREE_MAP_NODE_VALUE(node));
}

/*
 * Common Interface Functions
 */
static void
cmaid_tree_iter_attach(Cmaid_Container *c, Cmaid_Iter *it)
{
        it->interface = &cmaid_tree_key_iter_if;
        it->container = c;
        cmaid_tree_iter_start(it);

        /* insert into the iter list */
        it->next = CMAID_TREE(c)->iter_list;
        CMAID_TREE(c)->iter_list = it;
}

static void
cmaid_tree_iter_detach(Cmaid_Container *c, Cmaid_Iter *it)
{
        Cmaid_Tree *tree = CMAID_TREE(c);
        cmaid_iterlist_remove(&tree->iter_list, it);
}

static void
cmaid_tree_node_destroy_recrusive(Cmaid_Tree *tree, Cmaid_Tree_Node *node,
                Cmaid_Container_Node_Free_Cb node_free)
{
        if (node->left)
                cmaid_tree_node_destroy_recrusive(tree, node->left, node_free);
        if (node->right)
                cmaid_tree_node_destroy_recrusive(tree, node->right, node_free);
        node_free(CMAID_CONTAINER(tree), node);
}

static void
cmaid_tree_clear(Cmaid_Container *c)
{
        Cmaid_Tree *tree = CMAID_TREE(c);
        Cmaid_Container_Node_Free_Cb node_free;
        Cmaid_Tree_Node *node;

        node_free = CMAID_CONTAINER_FUNC(c)->node_free;

        if ((node = tree->root))
        {
                cmaid_tree_node_destroy_recrusive(tree, node, node_free);
                tree->root = NULL;
                CMAID_CONTAINER(tree)->count = 0;
        }

        return;
}

static void
cmaid_tree_node_dump(Cmaid_Tree_Node *node, FILE *file, char *buffer,
                        unsigned int size, Cmaid_Value_Stringify_Cb cb)
{
        /* first print the node */
        cb(node->key, buffer, size);
        fprintf(file, "\tn%p [label=\"%s\"];\n", node, buffer);

        /* and now the children */
        if (node->left)
        {
                cmaid_tree_node_dump(node->left, file, buffer, size, cb);
                fprintf(file, "\tn%p -> n%p\n", node, node->left);
        }
        if (node->right)
        {
                cmaid_tree_node_dump(node->right, file, buffer, size, cb);
                fprintf(file, "\tn%p -> n%p\n", node, node->right);
        }
}

static int
cmaid_tree_dump(Cmaid_Container *c, FILE *file)
{
        Cmaid_Tree *tree = CMAID_TREE(c);
        Cmaid_Value_Stringify_Cb cb;
        char buffer[1024];

        cb = tree->key_info->stringify ? tree->key_info->stringify :
                                        cmaid_value_pointer_stringify;

        fprintf(file, "digraph tree%p {\n", c);
        fprintf(file, "\tn%p [label=\"HEAD\"];\n", tree);
        if (tree->root)
        {
                fprintf(file, "\tn%p -> n%p\n", tree, tree->root);
                cmaid_tree_node_dump(tree->root, file, buffer, sizeof(buffer),
                                cb);
        }
        fprintf(file, "}\n");

        return TRUE;
}

static void
cmaid_tree_destroy(Cmaid_Container *c)
{
        cmaid_container_clear(c);
        FREE(c);
}

/*
 * The Set Interface Functions
 */
/**
 * @param v The @ref Cmaid_Value "value structure" defining the type of the
 *        objects used in the set
 * @return Returns a newly allocated @ref Cmaid_Set "set", an allocation error
 *        occurs, @c NULL is returned
 * @brief Creates a new set using the tree implementation
 *
 * This functions is creating a @ref Cmaid_Set "set" with the tree
 * as implementation.
 */
Cmaid_Set *
cmaid_tree_set_new(const Cmaid_Value *v)
{
        Cmaid_Tree *new_tree = CALLOC(1, sizeof(Cmaid_Tree));
        if (!new_tree)
                return NULL;

        CMAID_CONTAINER_INTERFACE_SET(new_tree, &cmaid_tree_set_if);
        if (v)
                new_tree->key_info = v;
        else
                new_tree->key_info = &cmaid_value_pointer;

        return (Cmaid_Set *)new_tree;
}

static void *
cmaid_tree_set_add(Cmaid_Set *set, const void *key)
{
        Cmaid_Tree *tree = CMAID_TREE(set);
        Cmaid_Tree_Node *find;

        if (cmaid_tree_node_get(tree, key, &find))
        {
                if (tree->key_info->pointer.free &&
                                !tree->key_info->pointer.dup)
                        tree->key_info->pointer.free((void *)key);
        }
        else
        {
                void *val;
                Cmaid_Tree_Node *node;

                node = cmaid_single_node_new(sizeof(Cmaid_Tree_Node),
                                tree->key_info, key, 0, &val);
                if (!node)
                        return NULL;

                node->key = val;
                cmaid_tree_iter_update_insert(tree, node);
                cmaid_tree_node_insert(tree, node, find);

                return val;
        }

        return find->key;
}

static void
cmaid_tree_set_remove(Cmaid_Set *set, const void *key)
{
        Cmaid_Tree_Node *node;
        Cmaid_Tree *tree = CMAID_TREE(set);

        if (!cmaid_tree_node_get(tree, key, &node))
                return;

        cmaid_tree_iter_update_remove_data(tree, node);
        cmaid_tree_node_remove(tree, node);
        cmaid_tree_single_node_free(set, node);
}

static void *
cmaid_tree_set_get(Cmaid_Set *set, const void *key)
{
        Cmaid_Tree_Node *node;
        Cmaid_Tree *tree = CMAID_TREE(set);

        if (cmaid_tree_node_get(tree, key, &node))
                return node->key;

        return NULL;
}

/*
 * The Map Interface Functions
 */
static void
cmaid_tree_map_value_iter_attach(Cmaid_Container *c, Cmaid_Iter *it)
{
        it->interface = &cmaid_tree_value_iter_if;
        it->container = c;
        cmaid_tree_iter_start(it);

        /* insert into the iter list */
        it->next = CMAID_TREE(c)->iter_list;
        CMAID_TREE(c)->iter_list = it;
}

/**
 * @param key The @ref Cmaid_Value "value structure" defining the type of the
 *        objects used for the key object.
 * @param value The @ref Cmaid_Value "value structure" defining the type of the
 *        objects used for the value object.
 * @return Returns a newly allocated @ref Cmaid_Map "map", an allocation error
 *        occurs, @c NULL is returned.
 * @brief Creates a new map using the tree implementation
 *
 * This functions is creating a @ref Cmaid_Map "map" with the tree as
 * implementation.
 */
Cmaid_Map *
cmaid_tree_map_new(const Cmaid_Value *key, const Cmaid_Value *value)
{
        Cmaid_Tree *new_tree = CALLOC(1, sizeof(Cmaid_Tree_Map));
        if (!new_tree)
                return NULL;

        CMAID_CONTAINER_INTERFACE_SET(new_tree, &cmaid_tree_map_if);
        if (key)
                new_tree->key_info = key;
        else
                new_tree->key_info = &cmaid_value_pointer;

        if (value)
                CMAID_TREE_MAP_VALUE_INFO(new_tree) = value;
        else
                CMAID_TREE_MAP_VALUE_INFO(new_tree) = &cmaid_value_pointer;

        return (Cmaid_Map *)new_tree;
}

static void *
cmaid_tree_map_set(Cmaid_Map *map, const void *key, const void *value)
{
        Cmaid_Tree *tree = CMAID_TREE(map);
        Cmaid_Tree_Node *find;
        Cmaid_Tree_Node *new_node;
        unsigned int size = 0;

        if (cmaid_tree_node_get(tree, key, &find))
        {
                void *ptr_key;

                if (tree->key_info->pointer.free && !tree->key_info->pointer.dup)
                        tree->key_info->pointer.free((void *)key);

                if (CMAID_TREE_MAP_VALUE_INFO(tree)->pointer.free)
                        CMAID_TREE_MAP_VALUE_INFO(tree)->pointer.free(CMAID_TREE_MAP_NODE_VALUE(find));

                /* get the size of the key */
                if (tree->key_info->size < 0)
                        size = tree->key_info->sized.size(find->key);
                else
                        size = tree->key_info->size;

                new_node = cmaid_pair_node_renew(find,
                                sizeof(Cmaid_Tree_Node_Pair),
                                size, CMAID_TREE_MAP_VALUE_INFO(tree),
                                value, &ptr_key);

                CMAID_TREE_MAP_NODE_VALUE(new_node) = ptr_key;
                if (new_node != find)
                {
                        cmaid_tree_node_repair(tree, find, new_node);
                        cmaid_iterlist_repair(tree->iter_list, find, new_node);
                        
                }
        }
        else
        {
                void *vptr;
                void *kptr;
                new_node = cmaid_pair_node_new(sizeof(Cmaid_Tree_Node_Pair),
                                tree->key_info, key, size, &kptr,
                                CMAID_TREE_MAP_VALUE_INFO(tree), value, 0,
                                &vptr);
                if (!new_node)
                        return NULL;

                new_node->key = kptr;
                CMAID_TREE_MAP_NODE_VALUE(new_node) = vptr;
                cmaid_tree_iter_update_insert(tree, new_node);
                cmaid_tree_node_insert(tree, new_node, find);
                return kptr;
        }

        return new_node->key;
}

static void
cmaid_tree_map_remove(Cmaid_Map *map, const void *key)
{
        Cmaid_Tree_Node *find;
        Cmaid_Tree *tree = CMAID_TREE(map);

        /* Compute the position in the table */
        if (cmaid_tree_node_get(tree, key, &find))
        {
                cmaid_tree_iter_update_remove_data(tree, find);
                cmaid_tree_node_remove(tree, find);
                cmaid_tree_map_node_free(map, find);
        }
}

static void *
cmaid_tree_map_get(Cmaid_Map *map, const void *key)
{
        Cmaid_Tree_Node *find;
        Cmaid_Tree *tree = CMAID_TREE(map);

        if (cmaid_tree_node_get(tree, key, &find))
                return CMAID_TREE_MAP_NODE_VALUE(find);

        return NULL;
}


/*
 * Helper functions
 */
static void
cmaid_tree_node_repair(Cmaid_Tree *tree, Cmaid_Tree_Node *old_node,
                        Cmaid_Tree_Node *new_node)
{
        Cmaid_Tree_Node *parent;

        if ((parent = new_node->parent))
        {
                if (parent->left == old_node)
                        parent->left = new_node;
                else
                        parent->right = new_node;
        }
        else
                tree->root = new_node;

        if (new_node->left)
                new_node->left->parent = new_node;
        if (new_node->right)
                new_node->right->parent = new_node;
}

static void
cmaid_tree_iter_update_remove_index(Cmaid_Tree *tree, Cmaid_Tree_Node *node,
                int index)
{
        Cmaid_Iter *it;

        for (it = tree->iter_list; it; it = it->next)
        {
                if (it->current == node)
                        it->current = cmaid_tree_node_previous(node);
                if (it->index >= index)
                        it->index--;
        }
}

static void
cmaid_tree_iter_update_remove_data(Cmaid_Tree *tree, Cmaid_Tree_Node *node)
{
        Cmaid_Iter *it;
        Cmaid_Value_Compare_Cb cmp = tree->key_info->cmp;

        for (it = tree->iter_list; it; it = it->next)
        {
                Cmaid_Tree_Node *cur = it->current;

                if (it->current == node)
                {
                        it->current = cmaid_tree_node_previous(node);
                        it->index--;
                }
                else if ((cmp && cmp(cur->key, node->key) > 0)
                        || (!cmp && cur->key > node->key))
                        it->index--;
        }
}

static void
cmaid_tree_iter_update_insert(Cmaid_Tree *tree, Cmaid_Tree_Node *node)
{
        Cmaid_Iter *it;
        Cmaid_Value_Compare_Cb cmp = tree->key_info->cmp;

        for (it = tree->iter_list; it; it = it->next)
        {
                Cmaid_Tree_Node *cur = it->current;

                if (!cur)
                        continue;
                if ((cmp && cmp(cur->key, node->key) > 0)
                        || (!cmp && cur->key > node->key))
                        it->index++;
        }
}

/*
 * The Iterator functions
 */
/* The common iterator interface functions */
static void
cmaid_tree_iter_start(Cmaid_Iter *it)
{
        it->current = NULL;
        it->index = -1;
}

static void
cmaid_tree_iter_remove(Cmaid_Iter *it)
{
        Cmaid_Tree *tree = CMAID_TREE(it->container);
        Cmaid_Tree_Node *node = it->current;

        if (node)
        {
                cmaid_tree_iter_update_remove_index(tree, node, it->index);
                cmaid_tree_node_remove(tree, node);
                CMAID_CONTAINER_FUNC(CMAID_CONTAINER(it->container))->node_free(it->container,
                                node);
        }
}

/* helper functions */
static Cmaid_Tree_Node *
cmaid_tree_iter_next(Cmaid_Iter *it)
{
        /* if we at the start the index is -1 so ++ is here correct, too.
         * if we at the last node, we will correct the index at the end */
        it->index++;
        if (it->current)
                it->current = cmaid_tree_node_next(it->current);
        else
        {
                Cmaid_Tree_Node *node;
                const Cmaid_Tree *tree = CMAID_TREE(it->container);
                
                if ((node = tree->root))
                {
                        while (node->left)
                                node = node->left;
                        it->current = node;
                }
                else
                        it->current = NULL;
        }

        if (!it->current)
                it->index = -1;

        return it->current;
}

static Cmaid_Tree_Node *
cmaid_tree_iter_previous(Cmaid_Iter *it)
{
        it->index--;
        if (it->current)
                it->current = cmaid_tree_node_previous(it->current);
        else
        {
                Cmaid_Tree_Node *node;
                const Cmaid_Tree *tree = CMAID_TREE(it->container);
                
                if ((node = tree->root))
                {
                        while (node->right)
                                node = node->right;
                        it->current = node;
                        it->index = CMAID_CONTAINER(it->container)->count - 1;
                }
                else
                {
                        it->current = NULL;
                        it->index = -1;
                }
        }

        return it->current;
}

static Cmaid_Tree_Node *
cmaid_tree_iter_index_goto(Cmaid_Iter *it, int index)
{
        const int count = CMAID_CONTAINER(it->container)->count;
        int i;

        if (count == 0 || index >= count || index < 0)
        {
                cmaid_tree_iter_start(it);
                return NULL;
        }

        if (index < it->index)
                cmaid_tree_iter_start(it);

        for (i = it->index; i != index; i++)
                cmaid_tree_iter_next(it);

        return it->current;
}

/* The key iter functions */
static void *
cmaid_tree_key_iter_iter_goto(Cmaid_Iter *it, const Cmaid_Iter *to_it)
{
        if (!to_it || it->container != to_it->container)
                return NULL;

        it->index = to_it->index;
        it->current = to_it->current;
        return (it->current) ? CMAID_TREE_NODE(it->current)->key : NULL;
}

static void *
cmaid_tree_key_iter_index_goto(Cmaid_Iter *it, int index)
{
        Cmaid_Tree_Node *node = cmaid_tree_iter_index_goto(it, index);
        return (node) ? node->key : NULL;
}

static void *
cmaid_tree_key_iter_goto(Cmaid_Iter *it, const void *data)
{
        void * found;

        cmaid_tree_iter_start(it);
        while ((found = cmaid_tree_key_iter_next(it)) && found != data)
                ;

        return found;
}

static void *
cmaid_tree_key_iter_current(Cmaid_Iter *it)
{
        return (it->current) ? CMAID_TREE_NODE(it->current)->key : NULL;
}

static void *
cmaid_tree_key_iter_next(Cmaid_Iter *it)
{
        Cmaid_Tree_Node *node = cmaid_tree_iter_next(it);
        return (node) ? node->key : NULL;
}

static void *
cmaid_tree_key_iter_previous(Cmaid_Iter *it)
{
        Cmaid_Tree_Node *node = cmaid_tree_iter_previous(it);
        return (node) ? node->key : NULL;
}

/* The value iter functions */
static void *
cmaid_tree_value_iter_iter_goto(Cmaid_Iter *it, const Cmaid_Iter *to_it)
{
        if (!to_it || it->container != to_it->container)
                return NULL;

        it->index = to_it->index;
        it->current = to_it->current;
        return (it->current) ? CMAID_TREE_MAP_NODE_VALUE(it->current) : NULL;
}
static void *
cmaid_tree_value_iter_index_goto(Cmaid_Iter *it, int index)
{
        Cmaid_Tree_Node *node = cmaid_tree_iter_index_goto(it, index);
        return (node) ? CMAID_TREE_MAP_NODE_VALUE(node) : NULL;
}

static void *
cmaid_tree_value_iter_goto(Cmaid_Iter *it, const void *data)
{
        void * found;

        cmaid_tree_iter_start(it);
        while ((found = cmaid_tree_value_iter_next(it)) && found != data)
                ;

        return found;
}

static void *
cmaid_tree_value_iter_current(Cmaid_Iter *it)
{
        return (it->current) ? CMAID_TREE_MAP_NODE_VALUE(it->current) : NULL;
}

static void *
cmaid_tree_value_iter_next(Cmaid_Iter *it)
{
        Cmaid_Tree_Node *node = cmaid_tree_iter_next(it);
        return (node) ? CMAID_TREE_MAP_NODE_VALUE(node) : NULL;
}

static void *
cmaid_tree_value_iter_previous(Cmaid_Iter *it)
{
        Cmaid_Tree_Node *node = cmaid_tree_iter_previous(it);
        return (node) ? CMAID_TREE_MAP_NODE_VALUE(node) : NULL;
}

/*
 * The Balancing code for the Red-Black-Tree
 *
 * For the rb tree must fulfill the same rules like an ordinary search tree,
 * besides that, there are other rules that needs to be met.
 *
 * 1. Every node is red or black
 * 2. The root is black
 * 3. All leafs (NULL-nodes) are black
 * 4. Both children of a red node are black
 * 5. Every path from a node to any leaf has the same count of black nodes
 *
 */

#define RB_SET(elm, parent) do {                                        \
        RB_PARENT(elm) = parent;                                        \
        RB_LEFT(elm) = RB_RIGHT(elm) = NULL;                                \
        RB_COLOR(elm) = RB_RED;                                                  \
} while (/*CONSTCOND*/ 0)

#define RB_SET_BLACKRED(black, red) do {                                \
        RB_COLOR(black) = RB_BLACK;                                        \
        RB_COLOR(red) = RB_RED;                                                \
} while (/*CONSTCOND*/ 0)

/*
 *   node                       right
 *    /\                         / \
 *   /  \                       /   \
 *  L  right       ----->     node  RGC
 *      / \                    /\
 *     /   \                  /  \
 *    LGC  RGC               L   LGC
 *
 * Left-rotates the subtree with node as root, the right child node will
 * become the new subtree root.
 */
CMAID_INLINE void
cmaid_tree_rotate_left(Cmaid_Tree *tree, Cmaid_Tree_Node *node)
{
        Cmaid_Tree_Node *right = RB_RIGHT(node);

        if ((RB_RIGHT(node) = RB_LEFT(right)))
                RB_PARENT(RB_LEFT(right)) = node;

        if ((RB_PARENT(right) = RB_PARENT(node)))
        {
                if (node == RB_LEFT(RB_PARENT(node)))
                        RB_LEFT(RB_PARENT(node)) = right;
                else
                        RB_RIGHT(RB_PARENT(node)) = right;
        }
        else
                tree->root = right;

        RB_LEFT(right) = node;
        RB_PARENT(node) = right;
}

/*
 *      node                   right
 *       /\                     / \
 *      /  \                   /   \
 *    left  R     ----->     node  RGC
 *    / \                    /\
 *   /   \                  /  \
 *  LGC  RGC               L   LGC
 *
 * Left-rotates the subtree with node as root, the right child node will
 * become the new subtree root.
 */
inline void
cmaid_tree_rotate_right(Cmaid_Tree *tree, Cmaid_Tree_Node *node)
{
        Cmaid_Tree_Node *left = RB_LEFT(node);

        if ((RB_LEFT(node) = RB_RIGHT(left)))
                RB_PARENT(RB_RIGHT(left)) = node;

        if ((RB_PARENT(left) = RB_PARENT(node)))
        {
                if (node == RB_LEFT(RB_PARENT(node)))
                        RB_LEFT(RB_PARENT(node)) = left;
                else
                        RB_RIGHT(RB_PARENT(node)) = left;
        }
        else
                tree->root = left;

        RB_RIGHT(left) = node;
        RB_PARENT(node) = left;
}

/* 
 * The node is already inserted into the tree. This function will
 * rebalance the tree.
 */
static void
cmaid_tree_insert_color(Cmaid_Tree *tree, Cmaid_Tree_Node *node)
{
        Cmaid_Tree_Node *parent;

        /* we are done if the parent is black, because the node is red
         * the black path length does not change, inside of the loop
         * we have to deal with the violation of the rule 4, i.e.
         * the (red) node has a red parent */
        while ((parent = RB_PARENT(node)) && RB_COLOR(parent) == RB_RED)
        {
                /* Since the parent is red it cannot be the root, this means
                 * that there must be a grandparent, and since it was
                 * a valid RB-tree before the grandparent must be black */
                Cmaid_Tree_Node *gparent = RB_PARENT(parent);

                if (parent == RB_LEFT(gparent))
                {
                        Cmaid_Tree_Node *uncle = RB_RIGHT(gparent);

                        /* the parent and the uncle are both red */
                        if (RB_IS_RED(uncle))
                        {
                                /* we simply recolor the parent and the uncle
                                 * to black, to fulfill rule 5 we have to
                                 * recolor the grandparent to red */
                                RB_COLOR(uncle) = RB_BLACK;
                                RB_SET_BLACKRED(parent, gparent);
                                /* since we recolor the grandparent to red, 
                                 * he might violate now rule 4, i.e.
                                 * restart the loop with the grandparent as
                                 * the new node */
                                node = gparent;
                                continue;
                        }
                        if (RB_RIGHT(parent) == node)
                        {
                                /* The tree looks like this (lowercase, and
                                 * numbers = black, uppercase = red)
                                 *
                                 *        g
                                 *       / \
                                 *      /   \
                                 *     P     u
                                 *    / \   / \
                                 *   /   \
                                 *  1     N
                                 *       / \
                                 *      2   3
                                 *
                                 * We now rotate the the parent, since both
                                 * parent and node are red this will not change
                                 * the black path length, so we do not 
                                 * violate rule 5
                                 */
                                cmaid_tree_rotate_left(tree, parent);
                                /* the old parent is now the child of the node
                                 * we need to swap those values, we use
                                 * the uncle as temporal variable, because
                                 * we do not need it anymore */
                                uncle = parent;
                                parent = node;
                                node = uncle;
                        }
                        /* After the rotation before the subtree looks now in
                         * any case like this:
                         *          g
                         *         / \
                         *        /   \
                         *       P     u
                         *      / \   / \
                         *     /   \
                         *    N     3
                         *   / \
                         *  1   2
                         *
                         *  We right rotate the tree and then toggle the colors
                         *  of the parent and the grandparent, this will
                         *  fullfil rule 5 and repair the rule 4.
                         *
                         *          p
                         *         / \
                         *        /   \
                         *       N     G
                         *      / \   / \
                         *     1   2 3   u
                         *              / \
                         *
                         */
                        cmaid_tree_rotate_right(tree, gparent);
                        RB_SET_BLACKRED(parent, gparent);
                        /* the tree is now repaired, the loop will stop, because
                         * the parent is now black */
                }
                /* the steps here are exactly the same like in the block
                 * before, but mirrored
                 */
                else
                {
                        Cmaid_Tree_Node *uncle = RB_LEFT(gparent);

                        if (RB_IS_RED(uncle))
                        {
                                RB_COLOR(uncle) = RB_BLACK;
                                RB_SET_BLACKRED(parent, gparent);
                                node = gparent;
                                continue;
                        }
                        if (RB_LEFT(parent) == node)
                        {
                                cmaid_tree_rotate_right(tree, parent);
                                uncle = parent;
                                parent = node;
                                node = uncle;
                        }
                        RB_SET_BLACKRED(parent, gparent);
                        cmaid_tree_rotate_left(tree, gparent);
                }
        }
        /* fulfill rule 2 */
        RB_COLOR(tree->root) = RB_BLACK;
}

static void
cmaid_tree_remove_color(Cmaid_Tree *tree, Cmaid_Tree_Node *parent,
                        Cmaid_Tree_Node *elm)
{
        Cmaid_Tree_Node *tmp;

        while (RB_IS_BLACK(elm) && elm != tree->root)
        {
                if (RB_LEFT(parent) == elm)
                {
                        tmp = RB_RIGHT(parent);
                        if (RB_COLOR(tmp) == RB_RED)
                        {
                                RB_SET_BLACKRED(tmp, parent);
                                cmaid_tree_rotate_left(tree, parent);
                                tmp = RB_RIGHT(parent);
                        }
                        if (RB_IS_BLACK(RB_LEFT(tmp))
                                        && RB_IS_BLACK(RB_RIGHT(tmp)))
                        {
                                RB_COLOR(tmp) = RB_RED;
                                elm = parent;
                                parent = RB_PARENT(elm);
                        }
                        else
                        {
                                if (RB_IS_BLACK(RB_RIGHT(tmp)))
                                {
                                        Cmaid_Tree_Node *oleft;
                                        if ((oleft = RB_LEFT(tmp)))
                                                RB_COLOR(oleft) = RB_BLACK;
                                        RB_COLOR(tmp) = RB_RED;
                                        cmaid_tree_rotate_right(tree, tmp);
                                        tmp = RB_RIGHT(parent);
                                }
                                RB_COLOR(tmp) = RB_COLOR(parent);
                                RB_COLOR(parent) = RB_BLACK;
                                if (RB_RIGHT(tmp))
                                        RB_COLOR(RB_RIGHT(tmp)) = RB_BLACK;
                                cmaid_tree_rotate_left(tree, parent);
                                elm = tree->root;
                                break;
                        }
                } 
                else 
                {
                        tmp = RB_LEFT(parent);
                        if (RB_COLOR(tmp) == RB_RED)
                        {
                                RB_SET_BLACKRED(tmp, parent);
                                cmaid_tree_rotate_right(tree, parent);
                                tmp = RB_LEFT(parent);
                        }
                        if (RB_IS_BLACK(RB_LEFT(tmp)) 
                                        && RB_IS_BLACK(RB_RIGHT(tmp)))
                        {
                                RB_COLOR(tmp) = RB_RED;
                                elm = parent;
                                parent = RB_PARENT(elm);
                        }
                        else
                        {
                                if (RB_IS_BLACK(RB_LEFT(tmp)))
                                {
                                        Cmaid_Tree_Node *oright;
                                        if ((oright = RB_RIGHT(tmp)))
                                                RB_COLOR(oright) = RB_BLACK;
                                        RB_COLOR(tmp) = RB_RED;
                                        cmaid_tree_rotate_left(tree, tmp);
                                        tmp = RB_LEFT(parent);
                                }
                                RB_COLOR(tmp) = RB_COLOR(parent);
                                RB_COLOR(parent) = RB_BLACK;
                                if (RB_LEFT(tmp))
                                        RB_COLOR(RB_LEFT(tmp)) = RB_BLACK;
                                cmaid_tree_rotate_right(tree, parent);
                                elm = tree->root;
                                break;
                        }
                }
        }
        if (elm)
                RB_COLOR(elm) = RB_BLACK;
}

Cmaid_Tree_Node *
cmaid_tree_node_remove(Cmaid_Tree *tree, Cmaid_Tree_Node *elm)
{
        Cmaid_Tree_Node *child, *parent, *old = elm;
        int color;

        if (!RB_LEFT(elm))
                child = RB_RIGHT(elm);
        else if (!RB_RIGHT(elm))
                child = RB_LEFT(elm);
        else
        {
                Cmaid_Tree_Node *left;

                elm = RB_RIGHT(elm);
                while ((left = RB_LEFT(elm)))
                        elm = left;
                child = RB_RIGHT(elm);
                parent = RB_PARENT(elm);
                color = RB_COLOR(elm);
                if (child)
                        RB_PARENT(child) = parent;
                if (parent)
                {
                        if (RB_LEFT(parent) == elm)
                                RB_LEFT(parent) = child;
                        else
                                RB_RIGHT(parent) = child;
                }
                else
                        tree->root = child;

                if (RB_PARENT(elm) == old)
                        parent = elm;
                
                elm->parent = old->parent;
                elm->left = old->left;
                elm->right = old->right;
                elm->color = old->color;

                cmaid_tree_node_repair(tree, old, elm);

                goto color;
        }
        parent = RB_PARENT(elm);
        color = RB_COLOR(elm);
        if (child)
                RB_PARENT(child) = parent;
        if (parent)
        {
                if (RB_LEFT(parent) == elm)
                        RB_LEFT(parent) = child;
                else
                        RB_RIGHT(parent) = child;
        }
        else
                tree->root = child;
color:
        if (color == RB_BLACK)
                cmaid_tree_remove_color(tree, parent, child);

        CMAID_CONTAINER(tree)->count--;
        return old;
}

/* Inserts a node into the RB tree */
static void
cmaid_tree_node_insert(Cmaid_Tree *tree, Cmaid_Tree_Node *node,
                        Cmaid_Tree_Node *parent)
{
        RB_SET(node, parent);
        if (parent)
        {
                if (tree->key_info->cmp)
                {
                        if (tree->key_info->cmp(node->key, parent->key) < 0)
                                RB_LEFT(parent) = node;
                        else
                                RB_RIGHT(parent) = node;
                }
                else if (node->key < parent->key)
                        RB_LEFT(parent) = node;
                else
                        RB_RIGHT(parent) = node;
        }
        else
                tree->root = node;

        cmaid_tree_insert_color(tree, node);
        CMAID_CONTAINER(tree)->count++;
}

static unsigned int
cmaid_tree_node_get(Cmaid_Tree *tree, const void *key, Cmaid_Tree_Node **find)
{
        Cmaid_Tree_Node *cur = tree->root;
        Cmaid_Value_Compare_Cb cmp = tree->key_info->cmp;

        *find = cur;
        if (cmp)
        {
                while (cur)
                {
                        int comp = cmp(key, cur->key);

                        *find = cur;
                        if (comp < 0)
                                cur = RB_LEFT(cur);
                        else if (comp > 0)
                                cur = RB_RIGHT(cur);
                        else
                                return TRUE;
                }
        }
        else
        {
                while (cur)
                {
                        *find = cur;
                        if (key < cur->key)
                                cur = RB_LEFT(cur);
                        else if (key > cur->key)
                                cur = RB_RIGHT(cur);
                        else
                                return TRUE;
                }
        }
        return FALSE;
}

static Cmaid_Tree_Node *
cmaid_tree_node_next(Cmaid_Tree_Node *node)
{
        if (RB_RIGHT(node))
        {
                node = RB_RIGHT(node);
                while (RB_LEFT(node))
                        node = RB_LEFT(node);
        }
        else
        {
                if (RB_PARENT(node) && (node == RB_LEFT(RB_PARENT(node))))
                        node = RB_PARENT(node);
                else
                {
                        while (RB_PARENT(node)
                                        && (node == RB_RIGHT(RB_PARENT(node))))
                                node = RB_PARENT(node);
                        node = RB_PARENT(node);
                }
        }
        return node;
}

static Cmaid_Tree_Node *
cmaid_tree_node_previous(Cmaid_Tree_Node *node)
{
        if (RB_LEFT(node))
        {
                node = RB_LEFT(node);
                while (RB_RIGHT(node))
                        node = RB_RIGHT(node);
        }
        else
        {
                if (RB_PARENT(node) && (node == RB_RIGHT(RB_PARENT(node))))
                        node = RB_PARENT(node);
                else
                {
                        while (RB_PARENT(node)
                                        && (node == RB_LEFT(RB_PARENT(node))))
                                node = RB_PARENT(node);
                        node = RB_PARENT(node);
                }
        }
        return node;
}

